package Sort;

/**
 * 排序(1)
 * 选择排序
 * 找到数组中最小的元素，与第一个元素交换元素
 * 剩下的元素中再找最小的元素，与第二个交换位置，以此类推
 * （不断选择剩余元素中的最小值）
 * 假设数组元素数量为：N
 * 交换总次数固定为N
 * 因此时间效率取决于元素之间比较次数
 */
public class SelectionSort extends Template {

    //升序
    public static void sort(Comparable[] a) {
        int N = a.length;
        //System.out.println("排序过程:");
        for (int i = 0; i < N; i++) {
            //min为当前这次遍历中应该交换的下标（本次遍历最小元素的下标，默认为本次遍历的首元素下标）
            int min = i;
            //从当前默认最小值的下标的下一下标开始比较大小，后者小则更换min下标值
            for (int j = i + 1; j < N; j++) {
                if (less(a[j], a[min]))
                    min = j;
            }
            //本次遍历比较完所有元素后，交换下标为i和下标为min的值，使得min每次都位于剩余元素首部
            exch(a, i, min);
            //输出每次遍历的结果，查看排序过程
            //show(a);
        }
    }


//   无注释
//    public static void sort(Comparable[] a) {
//        int N = a.length;
//        for (int i = 0; i < N; i++) {
//            int min = i;
//            for (int j = i + 1; j < N; j++) {
//                if (less(a[j], a[min]))
//                    min = j;
//            }
//            exch(a, i, min);
//        }
//    }


    public static void main(String[] args) {
        // String[] a = {"c", "s", "d", "n", "x", "i", "n", "g", "w", "e", "i", "s", "h", "e", "l", "l", "s", "o", "r", "t"};
        Comparable[] a = Template.getData(20);
        System.out.println("选择排序前");

        show(a);
        sort(a);

        assert isSorted(a);
        System.out.println("选择排序后");
        show(a);
    }

}
